package editor.cn;

import java.util.Arrays;

class Solution122 {
    public static void main(String[] args) {
        Solution solution = new Solution122().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maxProfit(int[] prices) {
            //   方法1：直接贪遍历，就是将利润平摊即可！！整体买入等价于在每一天买入，直接前一天减去后一天，就是最大的利润。
            //    return iter(prices);

            //   方法2：dp。 dp[i]=dp[i-1]+Math.max((prices[i]-prices[i-1]),0);其实上面的iter就是这里推出来的。
            //    return dp(prices);

            //  方法3,灵神的统一解法(真的状态机无敌了属于！！)：f[i][1]与f[i][0]的转化.表示第i天持有与非持有的利润
            //return dp1(prices);

            //  方法4，灵神的大一统写法(当然最后内存会出现限制，这没关系！最后一个用例过不了)
            return dp2(prices);
        }

        private int dp2(int[] prices) {
            int n=prices.length;
            //实现3个维度，f[这是第几天][实现最多/最少几次交易][是否持有？]
            int[][][] dp = new int[n+1][n+2][2];
            for (int[][] ints : dp) {
                for (int[] anInt : ints) {
                    Arrays.fill(anInt,Integer.MIN_VALUE/2);
                }
            }
            for (int j = 1; j < n +2; j++) {
                dp[0][j][0]=0;
            }
            for (int i = 0; i < n ; i++) {
                for (int j  = 1; j < n+2; j++) {
                    dp[i+1][j][0]=Math.max(dp[i][j][0],dp[i][j][1]+prices[i]);
                    dp[i+1][j][1]=Math.max(dp[i][j][1],dp[i][j-1][0]-prices[i]);
                }
            }

            return dp[n][n+1][0];
        }


        private int dp1(int[] prices) {
            int n = prices.length;
            int[][] f = new int[n + 1][2];//两个维度，这里是dp[第i天][是否持有]
            f[0][1] = Integer.MIN_VALUE;
            //f[0][1]=0;
            for (int i = 0; i < n; i++) {
                f[i + 1][0] = Math.max(f[i][0], f[i][1] + prices[i]);
                f[i + 1][1] = Math.max(f[i][1], f[i][0] - prices[i]);
            }
            return f[n][0];
        }


        private int dp(int[] prices) {
            int n = prices.length;
            int[] dp = new int[n];//dp[i]=dp[i-1]+Math.max((prices[i]-price[i-1]),0);
            for (int i = 1; i < n; i++) {
                dp[i] = dp[i - 1] + Math.max((prices[i] - prices[i - 1]), 0);
            }
            return dp[n - 1];
        }

        private int iter(int[] prices) {
            int n = prices.length;
            //在0~n-1的天数里面，只收获正数的差值即可！！
            int r = 1;
            int sum = 0;
            for (; r < n; r++) {
                int profit = prices[r] - prices[r - 1];
                if (profit > 0) {
                    sum += profit;
                }
            }
            return sum;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}












